#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "../include/vfs.h"


bst* insert(bst *root,FD *data) {
        bst *newNode = (bst *) malloc(sizeof (bst));
        bst *temp;
	int flag=1;
           
        newNode->fileDesc  = data;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->parent = NULL;

        if(root == NULL){
                root = newNode;
        }
       
        else{
                temp=root;
                while(flag){
                        if(strcmp(newNode -> fileDesc -> path, temp -> fileDesc -> path) < 0){
                                if(temp -> left == NULL){
                                        newNode -> parent = temp;                
                                        temp -> left = newNode;
                                        flag=0;
                                }
                                else{
                                        temp = temp -> left;
                                }
                        }
                        else if(strcmp(newNode -> fileDesc -> path, temp -> fileDesc -> path) > 0){
                                if(temp -> right == NULL){
                                        newNode -> parent = temp;                
                                        temp -> right = newNode;
                                        flag=0;
                                }
                                else{
                                        temp = temp -> right;
                                }
                        }
                        else{
                                flag=0;
                        }
                }
        }

	return root;
}


void inorder(bst *t){
        if(t==NULL)
		return;
	
	else
	{
                inorder(t->left);
               // printf("\n fd filename: %s \tfd path: %s  \n",t->fileDesc->filename, t->fileDesc->path);
                inorder(t->right);
        }
}
 
void displayList(bst *root){
        bst *temp = root;
        if(root == NULL){
                // printf("\nEmpty tree\n");
        }
        else{
            inorder(temp);
        }
}
     
bst* search_bst(bst *t,char *data){
        if(t == NULL || (strcmp(data,t->fileDesc->path) ==0) || (strstr(t->fileDesc->path,data)!=NULL)){
                return t;
        }
        else{
                if( strcmp( data,t->fileDesc->path) <0 ){
                        return search_bst(t->left,data);
                }
                else{
                        return search_bst(t->right,data);
                }
         }
}


bst* searchResult(char *data,bst *root){
        bst *t = root;
        bst *temp = search_bst(t,data);
       
        if(temp == NULL) {
                return NULL;
        }
        else{
                return temp;
        }
}
   

   
void transplant(bst *u, bst *v,bst *root){
        if(u->parent == NULL){
                root = v;
        }
        else{
                if(u == u->parent->left){
                        u->parent->left = v;
                }
                else{
                        u->parent->right = v;
                }
        }
        if(v != NULL){
                v->parent = u->parent;
        }
}
   
   
bst* findMin(bst *m){
        while(m->left != NULL){
                m = m->left;
        }
       // printf("%s",m->fileDesc->path);
        return m;
}

void delete_bst(char *data,bst *root){
       
        bst* elem,*temp;
        bst* successor=NULL;
       
        temp = search_bst(root,data);

	while(temp)
	{	
       		elem = temp;
        	if(elem != NULL){
               	// printf("\nElement is present\n");
           	
               		 if(elem->left == NULL){
               		         transplant(elem,elem->right,root);
               		 }
                	else{
                        	if(elem->right==NULL){
                        	        transplant(elem,elem->left,root);
                        	}
                        	else{
                        	        successor = findMin(elem->right);
                        	        if(successor->parent != elem){
                        	                transplant( successor, successor->right,root);
                        	                successor->right = elem->right;
                      		                successor->right->parent =  successor;
                     		          }
                     	  	         transplant(elem, successor,root);
                     	  	         successor->left = elem->left;
                     	  	         successor->left->parent = successor;
                     	  	         successor->parent = elem->parent;
                     	
                        	}	
                	}	
                	free(elem);
			
			 temp = search_bst(root,data);
	}

	}
}
